class Solution {
public:
    bool hasCycle(ListNode* head)
    {
        if (!head) return false;
        if (head == head->next) return true;
        ListNode* fast = head, * slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int ret = nums[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

class Solution {
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (auto ch : s)
        {
            if (ch == '(' || ch == '{' || ch == '[')
            {
                st.push(ch);
            }
            else
            {
                if (st.empty()) return false;
                char top = st.top();
                if ((top == '(' && ch != ')') || (top == '[' && ch != ']') || (top == '{' && ch != '}')) return false;
                st.pop();
            }
        }
        if (st.size()) return false;
        return true;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        ListNode* newhead = new ListNode;
        ListNode* newtail = newhead;
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for (auto e : lists)
        {
            if (e) pq.push(e);
        }

        while (pq.size())
        {
            ListNode* top = pq.top();
            pq.pop();
            if (top->next) pq.push(top->next);
            newtail->next = top;
            newtail = newtail->next;
        }
        newtail->next = nullptr;
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }
};
class Solution {
public:
    string decodeString(string s)
    {
        stack<string> st1;
        stack<int> st2;
        st1.push("");

        for (int i = 0; i < s.size(); )
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + s[i] - '0';
                    i++;
                }
                st2.push(tmp);
            }
            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st1.push(tmp);
            }
            else if (s[i] == ']')
            {
                i++;
                string str = st1.top(); st1.pop();
                int num = st2.top(); st2.pop();
                string tmp;
                while (num--) tmp += str;
                st1.top() += tmp;
            }
            else
            {
                while (s[i] >= 'a' && s[i] <= 'z') st1.top() += s[i++];
            }
        }
        return st1.top();
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        ListNode* fast = head, * slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* newhead = new ListNode;
        ListNode* cur = slow, * next = cur->next;
        while (cur)
        {
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
            if (cur) next = cur->next;
        }
        ListNode* cur1 = head, * cur2 = newhead->next;
        while (cur1 && cur2)
        {
            if (cur1->val != cur2->val) return false;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return true;
    }
};
class Solution {
public:
    ListNode* partition(ListNode* head, int x)
    {
        if (!head || !head->next) return head;
        ListNode* newhead1 = new ListNode, * newtail1 = newhead1;
        ListNode* newhead2 = new ListNode, * newtail2 = newhead2;

        ListNode* cur = head;
        while (cur)
        {
            if (cur->val < x)
            {
                newtail1->next = cur;
                newtail1 = newtail1->next;
            }
            else
            {
                newtail2->next = cur;
                newtail2 = newtail2->next;
            }
            cur = cur->next;
        }
        newtail1->next = newhead2->next;
        newtail2->next = nullptr;
        ListNode* ret = newhead1->next;
        delete newhead1;
        delete newhead2;
        return ret; 0
    }
};